{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import YouTubeVideo\n",
    "\n",
    "YouTubeVideo(id=\"k4KHoLC7TFE\", width=\"100%\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our world, networks are an immensely useful _data modelling tool_\n",
    "to model complex _relational_ problems.\n",
    "Building on top of a network-oriented data model,\n",
    "they have been put to great use in a wide variety of settings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A _formal_ definition of networks\n",
    "\n",
    "Before we explore examples of networks,\n",
    "we want to first give you a more formal definition\n",
    "of what networks are.\n",
    "The reason is that knowing a _formal_ definition\n",
    "helps us refine our application of networks.\n",
    "So bear with me for a moment.\n",
    "\n",
    "In the slightly more academic literature,\n",
    "networks are more formally referred to as **graphs**.\n",
    "\n",
    "Graphs are comprised of two _sets_ of objects:\n",
    "\n",
    "- A **node set**: the \"entities\" in a graph.\n",
    "- An **edge set**: the record of \"relationships\" between the entities in the graph.\n",
    "\n",
    "For example, if a **node set** $n$ is comprised of elements:\n",
    "\n",
    "$$n = \\{a, b, c, d, ...\\}$$\n",
    "\n",
    "Then, the **edge set** $e$ would be represented as tuples of _pairs_ of elements:\n",
    "\n",
    "$$e = \\{(a, b), (a, c), (c, d), ...\\}$$\n",
    "\n",
    "If you extracted every node from the edge set $e$,\n",
    "it should form _at least a subset_ of the node set $n$.\n",
    "(It is at least a subset because not every node in $n$ might participate in an edge.)\n",
    "\n",
    "If you draw out a network, the \"nodes\" are commonly represented as shapes, such as circles,\n",
    "while the \"edges\" are the lines between the shapes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Examples of Networks\n",
    "\n",
    "Now that we have a proper definition of a graph,\n",
    "let's move on to explore examples of graphs.\n",
    "\n",
    "One example I (Eric Ma) am fond of, based on my background as a biologist,\n",
    "is a protein-protein interaction network.\n",
    "Here, the graph can be defined in the following way:\n",
    "\n",
    "- nodes/entities are the proteins,\n",
    "- edges/relationships are defined as \"one protein is known to bind with another\".\n",
    "\n",
    "A more colloquial example of networks is an air transportation network.\n",
    "Here, the graph can be defined in the following way:\n",
    "\n",
    "- nodes/entities are airports\n",
    "- edges/relationships are defined as \"at least one flight carrier flies between the airports\".\n",
    "\n",
    "And another even more relatable example would be our ever-prevalent social networks!\n",
    "With Twitter, the graph can be defined in the following way:\n",
    "\n",
    "- nodes/entities are individual users\n",
    "- edges/relationships are defined as \"one user has decided to follow another\".\n",
    "\n",
    "Now that you've seen the framework for defining a graph,\n",
    "we'd like to invite you to answer the following question:\n",
    "**What examples of networks have _you_ seen before in your profession?**\n",
    "\n",
    "Go ahead and list it out."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Types of Graphs\n",
    "\n",
    "As you probably can see, graphs are a really flexible data model\n",
    "for modelling the world,\n",
    "as long as the nodes and edges are strictly defined.\n",
    "(If the nodes and edges are _sloppily_ defined,\n",
    "well, we run into a lot of interpretability problems later on.)\n",
    "\n",
    "If you are a member of both LinkedIn and Twitter,\n",
    "you might intuitively think that there's a _slight_ difference\n",
    "in the structure of the two \"social graphs\".\n",
    "You'd be absolutely correct on that count!\n",
    "\n",
    "Twitter is an example of what we would intuitively call a **directed** graph.\n",
    "Why is this so?\n",
    "The key here lies in how interactions are modelled.\n",
    "One user can follow another, but the other need not necessarily follow back.\n",
    "As such, there is a _directionality_ to the relationship.\n",
    "\n",
    "LinkedIn is an example of what we would intuitively call an **undirected** graph.\n",
    "Why is this so?\n",
    "The key here is that when two users are LinkedIn connections,\n",
    "we _automatically_ assign a bi-directional edge between them.\n",
    "As such, for convenience, we can collapse the bi-directional edge\n",
    "into an _undirected_ edge,\n",
    "thus yielding an undirected graph.\n",
    "\n",
    "If we wanted to turn LinkedIn into a directed graph,\n",
    "we might want to keep information on who initiated the invitation.\n",
    "In that way, the relationship is automatically bi-directional."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Edges define the interesting part of a graph\n",
    "\n",
    "While in graduate school, I (Eric Ma) once sat in a seminar\n",
    "organized by one of the professors on my thesis committee.\n",
    "The speaker that day was John Quackenbush,\n",
    "a faculty member of the Harvard School of Public Health.\n",
    "While the topic of the day remained fuzzy in my memory,\n",
    "one quote stood out:\n",
    "\n",
    "> The heart of a graph lies in its edges, not in its nodes.\n",
    "> (John Quackenbush, Harvard School of Public Health)\n",
    "\n",
    "Indeed, this is a key point to remember!\n",
    "Without edges, the nodes are merely collections of entities.\n",
    "In a data table, they would correspond to the rows.\n",
    "That alone can be interesting,\n",
    "but doesn't yield _relational insights_ between the entities."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "nams",
   "language": "python",
   "name": "nams"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
